// #include <cstdlib>
// #include <iostream>
// namespace test
// {
//     int rand = 10;
    
//     int add(int a, int b)
//     {
//         return a + b;
//     }
// }

// int add(int a, int b = 10, int c = 10)
// {
//     return a + b + c;
// }

// //using std::cout;
// using namespace std;

// int main()
// {
    
//     //printf("%d", test::rand);
//     //cout << "hello world" << std::endl;

//     add(10, 20);

//     return 0;
// }

#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    //剑指 Offer 39. 数组中出现次数超过一半的数字
    //法一：哈希表
    int majorityElement(vector<int>& nums) {
        int haf = nums.size()/2;
        unordered_map<int, int> hash;
        for (auto num : nums)
        {
            ++hash[num];
        }
        for (auto hs : hash)
        {
            if (hs.second > haf)
            {
                return hs.first;
            }
        }
        return -1;
    }

    //法二：摩尔投票法
    int majorityElement(vector<int>& nums) {
        int candidate = 0;
        int voters = nums[0];
        for (auto num : nums)
        {
            if (voters == num)
            {
                ++candidate;
            }
            else if (--candidate < 0)
            {
                voters = num;
                candidate = 1;
            }
        }
        return voters;
    }
};